//
//  main.swift
//  LeetCode
//
//  Created by Abner Chen on 2017/7/28.
//  Copyright © 2017年 Abner Chen. All rights reserved.
//

import Foundation

/// 二叉树定义
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    
    /// 汉明距离
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        
        var tmpX = x
        var tmpY = y
        var count = 0
        
        while tmpX != 0 || tmpY != 0 {
            
            if tmpY & 1 != tmpX & 1{
                
                count += 1
            }
            
            tmpX = tmpX>>1 
            tmpY = tmpY>>1
        }
        
        return count
    }
    
    /*
     
     Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
     
     You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
     
     Input:
     Tree 1                     Tree 2
     1                         2
     / \                       / \
     3   2                     1   3
     /                           \   \
     5                             4   7
     Output:
     Merged tree:
     3
     / \
     4   5
     / \   \
     5   4   7
     
     */
    
    func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
        
        guard let t1 = t1 else {
            return t2
        }
        
        guard let t2 = t2 else {
            return t1
        }
        
        let newNode = TreeNode.init(t1.val + t2.val)
        
        newNode.left = mergeTrees(t1.left, t2.left)
        newNode.right = mergeTrees(t1.right, t2.right)
        
        return newNode
    }
    
    /*
     
     Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
     
     Example:
     Input: [1,4,3,2]
     
     Output: 4
     Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
     
     
     Note:
     n is a positive integer, which is in the range of [1, 10000].
     All the integers in the array will be in the range of [-10000, 10000].
     
     */
    func arrayPairSum(_ nums: [Int]) -> Int {
        
        let sorted = nums.sorted()
        
        var result = 0
        for i in stride(from: 0, to: nums.count, by: 2){
        
            result += sorted[i]
        }

        return result
    }
    
    /*
     
     Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
     
     Note:
     The given integer is guaranteed to fit within the range of a 32-bit signed integer.
     You could assume no leading zero bit in the integer’s binary representation.
     
     Example 1:
     Input: 5
     Output: 2
     Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
     
     Example 2:
     Input: 1
     Output: 0
     Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

     
     */
    func findComplement(_ num: Int) -> Int {
        
        /*  我的解决方案
        var result = 0
        var dat = Float.init(0)
        var tmp = num
        
        while tmp != 0 {
            
            result += Int(～(Float(tmp & 1)) * pow(2.0, dat))
            dat += 1
            tmp = tmp >> 1
        }
         return result
         
        */
        
        /* 方案二 代码最简
        var mask = 1
        while(mask <= num) {
            mask <<= 1
        }
        mask-=1
        
        return ~num & mask
        */
        
        
        // 效率最高
        var largestIndex = 0
        
        for i in 0 ..< 32 {
            
            if num & (0x1 << i) > 0 {
                largestIndex = i
            }
        }
        
        let mask = Int(Int32.max) >> (31 - largestIndex)
        
        return ~num & mask
    }
    
    /*
     
     Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
     
     pic = "https://leetcode.com/static/images/problemset/keyboard.png"
     
     Input: ["Hello", "Alaska", "Dad", "Peace"]
     Output: ["Alaska", "Dad"]
     
     */
    func findWords(_ words: [String]) -> [String] {
        
        /* 我的答案 对于swift函数使用不够灵活 可读性差
        let keyBoards = [["q","w","e","r","t","y","u","i","o","p"],
                        ["a","s","d","f","g","h","j","k","l"],
                        ["z","x","c","v","b","n","m"]]
        
        var res = [String]()
        for word in words{
            
            for line in keyBoards{
                
                var flag = 0
                for  alphabet in word.lowercased().characters {
                   
                    if !line.contains(alphabet.description) {
                        break
                    }
                    
                    flag += 1
                }
                if flag == word.characters.count {
                    
                    res.append(word)
                }
            }
        }
        
        return res
        */
        
        /*
         空间复杂度最低方案 利用了系统的方法直接判断集合的包含性
         */
        struct KeyboardRows {
            static let row1 : Set<Character> = ["q","w","e","r","t","y","u","i","o","p"]
            static let row2 : Set<Character> = ["a","s","d","f","g","h","j","k","l"]
            static let row3 : Set<Character> = ["z","x","c","v","b","n","m"]
        }
        
        var returnArray : [String] = []
        
        for word in words {
            
            let charSet = Set(word.lowercased().characters)
            
            if KeyboardRows.row1.isSuperset(of: charSet) {
                returnArray.append(word)
            }
            
            if KeyboardRows.row2.isSuperset(of: charSet) {
                returnArray.append(word)
            }
            
            if KeyboardRows.row3.isSuperset(of: charSet) {
                returnArray.append(word)
            }
        }
        
        return returnArray
    }
    
    
    /*
     
     Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
     
     Example 1:
     Input: "Let's take LeetCode contest"
     Output: "s'teL ekat edoCteeL tsetnoc"
     Note: In the string, each word is separated by single space and there will not be any extra space in the string.
     
     */
    func reverseWords(_ s: String) -> String {
        
        // 反转一个字符
        func reverse(_ s: String) -> String{
        
            var res = ""
            for ch in s.characters {
                res = String(ch) + res
            }
            return res
        }
        
        var res = ""
        let  tmp = s.components(separatedBy: " ")
        for word in tmp {
            res = res + reverse(word) + " "
        }
        res = res.substring(to: res.characters.endIndex)
        
        return res
    }
    
    /*
     
     Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
     
     You may assume the integer do not contain any leading zero, except the number 0 itself.
     
     The digits are stored such that the most significant digit is at the head of the list.
     
     Example 
     input: [1,3,9]
     
     output:[1,4,0]
     
     */
    func plusOne(_ digits: [Int]) -> [Int] {
        
        var res = digits
        let len = digits.count - 1
        for index in stride(from: len, through: 0, by: -1) {
            
            print(index)
            if res[index] < 9{
                
                res[index] += 1
                return res
            }
            
            res[index] = 0
        }
        
        res.insert(1, at: 0)
        
        return res
    }
    
    /*
     
     打印杨辉三角的第N层
     Given an index k, return the kth row of the Pascal's triangle.
     
     For example, given k = 3,
     Return [1,3,3,1].
     
     Note:
     Could you optimize your algorithm to use only O(k) extra space?
     
     */
    
    func getRow(_ rowIndex: Int) -> [Int] {
        
        // 保存了所有的数据
        var tmp = [[Int]]()
        
        // 外层
        tmp.append([1])
        tmp.append([1,1])
        
        if rowIndex < 1 {
            
            return tmp[rowIndex]
        }
        
        for row in 2...rowIndex{
        
            var rowTmp = [Int]()
            rowTmp.append(1)
            
            // 每一层
            for index in 1..<row{
                
                rowTmp.append(tmp[row - 1][index - 1] + tmp[row - 1][index])
            }
            
            rowTmp.append(1)
            tmp.append(rowTmp)
            
        }
        return tmp[rowIndex]
 
        
        // 仅计算需要的
//        var rst: [Int] = []
//        rst.append(1)
//        
//        var i = 1
//        while i <= rowIndex {
//            rst.append(0)
//            var j = rst.count - 1
//            while j > 0 {
//                rst[j] = rst[j] + rst[j-1]
//                j -= 1
//            }
//            i += 1
//        }
//        return rst
    }
    
    /*
     
     Given numRows, generate the first numRows of Pascal's triangle.
     
     For example, given numRows = 5,
     Return
     
     [
     [1],
     [1,1],
     [1,2,1],
     [1,3,3,1],
     [1,4,6,4,1]
     ]
     
     */
    func generate(_ numRows: Int) -> [[Int]] {
        
        var tmp = [[Int]]()
        
        for row in 0..<numRows{
            
            var rowTmp = [Int]()
            
            for index in 0...row{
                
                if index == 0 ||  index == row{
                    
                    rowTmp.append(1)
                }else {
                
                    rowTmp.append(tmp[row - 1][index - 1] + tmp[row - 1][index])
                }
            }
    
            tmp.append(rowTmp)
        }
        return tmp
    }
    
    /* 时间限制  空间不限制
     
     Given an array of integers, return indices of the two numbers such that they add up to a specific target.
     
     You may assume that each input would have exactly one solution, and you may not use the same element twice.
     
     Example:
     Given nums = [2, 7, 11, 15], target = 9,
     
     Because nums[0] + nums[1] = 2 + 7 = 9,
     return [0, 1].
     
     */
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

        /* 大量数据环境下 运行超时
        for index1 in stride(from: 0, to: nums.count, by: 1){
        
            for index2 in stride(from: 0, to: nums.count, by: 1){
                
                if index1 == index2 {
                    
                    continue
                }
                if nums[index1] + nums[index2] == target {
                    
                    return [index1, index2]
                }
            }
        }
        return [Int]();
         */
        
        var hashMap : [Int:Int] = [:]
        
        for (index, value) in nums.enumerated() {
            if let matchIndex = hashMap[target-value] {
                // 如果在当前value之前有(target－value)出现过，那么两者构成结果输出
                return [matchIndex, index]
            }
            
            hashMap[value] = index
        }
        
        return [0, 0]
    }
    
    /* 空间限制
     
     Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
     
     Find all the elements of [1, n] inclusive that do not appear in this array.
     
     Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
     
     Example:
     
     Input:
     [4,3,2,7,8,2,3,1]
     
     Output:
     [5,6]
     
     */
    func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
        
        
        // 第一种方法： 便利所有数据 放到hashMap里面  然后再次遍历hashMap  空间复杂度过高
        
        // 第二种方法： 不是太理解
        var res = [Int]()
        var tmpNums = nums
        
        for index in stride(from: 0, to: tmpNums.count, by: 1){
            let tmp = abs(tmpNums[index]) - 1
            if tmpNums[tmp] > 0{
                tmpNums[tmp] = -tmpNums[tmp]
            }
        }
        
        for index in stride(from: 0, to: tmpNums.count, by: 1){
           
            if tmpNums[index] > 0 {
                res.append(index + 1)
            }
        }
        return res
    }
    
    /* 数组去重 不得开辟新空间
     
     Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
     
     Do not allocate extra space for another array, you must do this in place with constant memory.
     
     For example,
     Given input array nums = [1,1,2],
     
     Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

     */
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        
        // 直观的最后一个和倒数第二个对比
        /*
        if nums.count < 2{
        
            return nums.count
        }
            
        for index in stride(from: (nums.count - 1), to: 0, by: -1){
        
            if nums[index] == nums[index - 1] {
                nums.remove(at: index)
            }
        }
        
        return nums.count
         */
        
        // 得分比较高的 不满足要求   返回数组没做变化
        if nums.count < 2{
            
            return nums.count
        }
        
        var j = 0
        for i in 1..<nums.count{
        
            if nums[i] != nums[j]{
                
                j += 1
                nums[j] = nums[i]
            }
        }
        
        return j + 1
    }
    
    /*
     
     Given an array and a value, remove all instances of that value in place and return the new length.
     
     Do not allocate extra space for another array, you must do this in place with constant memory.
     
     The order of elements can be changed. It doesn't matter what you leave beyond the new length.
     
     Example:
     Given input array nums = [3,2,2,3], val = 3
     
     Your function should return length = 2, with the first two elements of nums being 2.
     
     */
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        
        for index in stride(from: (nums.count - 1), through: 0, by: -1){
            
            if nums[index] == val {
                nums.remove(at: index)
            }
        }
        return nums.count
        
        // 产生新的数组
        // return nums.filter{$0 != val}.count
    }
    
    /*
     
     Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
     
     You may assume that the array is non-empty and the majority element always exist in the array.
     
     */
    func majorityElement(_ nums: [Int]) -> Int {
     
        var tmp = [Int:Int]()
        for i in nums{
        
            guard let count = tmp[i] else {
                
                tmp.updateValue(1, forKey: i)
                continue
            }
            tmp.updateValue(count + 1, forKey: i)
        }
        
        var maxCount = 0
        var max = 0
        for (key, value) in tmp {
            
            if value > maxCount {
                
                max = key
                maxCount = value
            }
        }
        
        return max
    }
    
    /*
     
     Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
     
     You need to find the shortest such subarray and output its length.
     
     Example 1:
     Input: [2, 6, 4, 8, 10, 9, 15]
     Output: 5
     Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
     Note:
     1. Then length of the input array is in range [1, 10,000].
     2. The input array may contain duplicates, so ascending order here means <=.
     
     */
    func findUnsortedSubarray(_ nums: [Int]) -> Int {
     
        
        
        return 3
    }
}


func call()  {
    
    let solution = Solution.init()
    
    // 汉明距离
    func hanmingDistanc(){
        
         let distance = solution.hammingDistance(4, 1)
         print(distance)
    }
    
    // 合并二叉树
    func mergeTree(){
        
        let t1 = TreeNode.init(5)
        t1.left = TreeNode.init(3)
        t1.right = TreeNode.init(3)
        t1.left?.left = TreeNode.init(2)
        t1.left?.right = TreeNode.init(1)
        t1.right?.right = TreeNode.init(3)
        
        let t2 = TreeNode.init(5)
        t2.left = TreeNode.init(3)
        t2.right = TreeNode.init(3)
        t2.left?.left = TreeNode.init(2)
        t2.left?.right = TreeNode.init(1)
        t2.right?.right = TreeNode.init(3)
        
        let tree = solution.mergeTrees(t1,t2)
        print(tree!)
    }
    
    func arrayPairSum(){
    
        let nums = [1,3,6,4,7,8,5,2]
//        let nums = [1,4,3,2]
        let res = solution.arrayPairSum(nums)
        
        print(res)
    }
    
    func findComplement(){
    
        let num = solution.findComplement(8)
        
        print(num)
    }
    
    func findWords(){
    
        let words = ["Hello", "Alaska", "Dad", "Peace"]
        
        let res = solution.findWords(words)
        
        print(res)
    }
    
    func reverseWord(){
    
        let res = solution.reverseWords("Let's take LeetCode contest")
        print(res)
    }
    
    func plusOne(){
    
        let res = solution.plusOne([9,9,9,9])

        print(res)
    }
    
    func getRow(){
    
    
        let res = solution.getRow(0)
        
        print(res)
    }
    
    func generate(){
    
        let res = solution.generate(0)
        
        print(res)
    }
    
    func twoSum(){
    
        let res = solution.twoSum([2,3,5], 8)
        
//        let input = 
        print(res)
    }
    
    func findDisappearedNumbers(){
    
        let res = solution.findDisappearedNumbers([1,2,3,4,4,6])
        print(res)
    }
    
    func removeDuplicates(){
    
        var input = [1,2,3,4,4,6,6]
        let res = solution.removeDuplicates(&input)
        
        print("count = \(res)\ninput:\(input)")
        
    }
    
    func removeElement(){
    
        var input = [1,2,3,3,4,5,3]
//        var input = [Int]();
        let res = solution.removeElement(&input, 3)
        
        print("count = \(res)\ninput:\(input)")
    }
    
    func majorityElement(){
    
        let res = solution.majorityElement([1,3,4,6,7,3,2,1,3,2,2,2,2])
        print(res)
    }
    
//    hanmingDistanc()
//    mergeTree()
//    arrayPairSum()
//    findComplement()
//    findWords()
//    reverseWord()
//    plusOne()
//    getRow()
//    generate()
//    twoSum()
//    findDisappearedNumbers()
//    removeDuplicates()
//    removeElement()
    majorityElement()
}

call()










